This disclosure relates generally to semiconductor device fabrication, and more particularly to the design of very large scale integrated (VLSI) semiconductor devices.
A design for a VLSI mask may include a plurality of rectilinear polygons that define the mask that is used in production of a semiconductor device. A typical VLSI mask design must be verified before the physical masks are created and the design is sent to production, as building a physical mask for use in production is an expensive process. Design faults in a VLSI design should be identified and eliminated as early as possible, before the physical mask is built. Design faults may be identified by performing a printability simulation of the VLSI design. However, a printability simulation of a VLSI design may be a computationally expensive task, especially for a full-chip simulation of a relatively large layout.
Verification of a VLSI mask may be performed using Fourier transforms of the polygons that make up the mask in order to analyze the polygons. In order to describe the polygons that make up a VLSI design, +1/−1 description may be used. This description allows relatively fast and accurate Fourier transforms of the polygons for simulation and analysis of lithographic processes to determine any design faults in a VLSI layout. The +1/−1 description of a mask comprises a two dimensional signal of +1's or <1's positioned at the corners of the polygons according to the following rules: the values of two adjacent corners of the same polygon are opposite (a+1 is followed by a −1 or vice-versa), and the value at any down-left corner of any polygon is always +1. This +1/−1 description is described in further detail in “Fast Continuous Haar and Fourier Transforms of Rectilinear Polygons from VLSI Layouts”, by Robin Scheibler, Paul Hurley, and Amina Chebira, arXiv:1010.5562 [cs.CE], 27 Oct. 2010, which is herein incorporated by reference in its entirety.